🔍搜索...K
QmksWeb

Appearance

《算法设计与分析》第一学期期末试卷A (精选04) ​

难度：⭐
考点：#渐近复杂度 #O记号 #Omega记号 #Theta记号 #极限比较

💡 学习锦囊

📖 相关公式与知识点

  • 定义：若存在 (c>0,n_0)，当 (n\ge n_0) 时，(f(n)\ge c,g(n))，则 (f(n)=\Omega(g(n)))：
  • 常用判别：若 (\lim_{n\to\infty} f(n)/g(n)=\infty)，则 (f(n)=\Omega(g(n)))。

易错点

  • 将( \log^2 n) 误当作(2\log n)（注意这里是平方）
  • 看到对数就直接下结论：(O(\log n))，忽略平方导致增长更快。
🔄 举一反三
  1. 比较 (f(n)=\log_2 n) ：(g(n)=\sqrt{\log_2 n}) 的渐近关系。
    查看练习答案与解析

    答案：(\log_2 n=\Omega(\sqrt{\log_2 n}))。

    解析：

    $$\lim_{n\to\infty}\frac{\log_2 n}{\sqrt{\log_2 n}} =\lim_{n\to\infty}\sqrt{\log_2 n} =+\infty$$

    故 (f=\Omega(g))。

  2. 比较 (f(n)=\log_2^3 n) ：(g(n)=n^\epsilon)（其中(\epsilon>0) 为常数）。
    查看练习答案与解析

    答案：(\log_2^3 n=o(n^\epsilon))，即 (g(n)=\Omega(f(n)))。

    解析（关键结论）：任意固定次幂对数都比任意正幂的多项式增长慢，可用极限。 (\lim_{n\to\infty}\log^k n / n^\epsilon = 0)（(k) 为常数）证明。

:::::

2. 给出汉诺塔递归算法，分析其时间复杂度： ​

txt
void Hanoi(int n,char x, char y, char z)
{
  if(n==1) printf("将盘片%d从%c搬到%c\n",n,x,z);
  else {
    Hanoi(n-1,x,z,y);
    printf("将盘片%d从%c搬到%c\n",n,x,z);
    Hanoi(n-1,y,x,z);
  }
}
查看答案与解析

答案：时间复杂度：(O(2^n))（更精确：执行打印次数为 (2^n-1)）。

解析（步骤完整）

  1. *建立递推案：设执行时间：(T(n))：
    • ：(n=1) 时，只执行一次打印，(T(1)=\Theta(1))：
    • ：(n>1) 时，算法包含两次规模：(n-1) 的递归调用：(O(1)) 次常数操作（一次打印）：
$$T(n)=2T(n-1)+\Theta(1).$$
  1. 展开递推：
$$\begin{aligned} T(n) &= 2T(n-1)+1\\ &= 2\bigl(2T(n-2)+1\bigr)+1 = 2^2T(n-2)+2+1\\ &= 2^3T(n-3)+2^2+2+1\\ &\;\;\vdots\\ &= 2^{n-1}T(1)+(2^{n-2}+2^{n-3}+\cdots+2+1) \\ &= 2^{n-1}\Theta(1) + (2^{n-1}-1) \\ &= \Theta(2^n). \end{aligned}$$

因此时间复杂度为 (O(2^n))，

方法总结：遇到“两个子问题规模都为 (n-1) + 常数工作量”，常见形式 (T(n)=2T(n-1)+O(1))，直接展开或用主定：递推求和即可。

难度：⭐
考点：#递归 #递推式 #时间复杂度 #汉诺塔

💡 学习锦囊

📖 相关公式与知识点

  • 经典递推：(T(n)=aT(n-1)+b\Rightarrow T(n)=\Theta(a^n))（当 (a>1) （(b=\Theta(1))）：
  • 汉诺塔移动次数：(M(1)=1)，(M(n)=2M(n-1)+1\Rightarrow M(n)=2^n-1)：

思路分析

先看“递归调用次数与规模”决定指数底数，再看“非递归部分”是常数还是线性等。

🔄 举一反三
  1. 若递推：(T(n)=3T(n-1)+2)，求 (T(n)) 的渐近复杂度：
    查看练习答案与解析

    答案：(\Theta(3^n))。

    解析：展开可得 (T(n)=3^{n-1}T(1)+2(3^{n-2}+ \cdots +1)=\Theta(3^n))：

  2. 若递推：(T(n)=2T(n-1)+n)，求 (T(n)) 的渐近复杂度：
    查看练习答案与解析

    答案：(\Theta(2^n))。

    解析（要点）：展开后出：(\sum_{k=1}^{n-1}2^{n-1-k}\cdot k)，该和为 (\Theta(2^n))，

3. 顺序查找算法如下，回答平均复杂度问题： ​

在长度为 (n) 的数：a[0..n-1] 中顺序查找值为 (x) 的元素，找到返回 1，否则返：0：

txt
int Find(double a[], int n, double x)
{
  int i = 0;
  while (i < n)
  {
    if (a[i] == x) break;
    i++;
  }
  if (i < n) return 1;
  else return 0;
}

回答案

  • 案）在“成功查找且每个位置等概率”的条件下，最优最优平均时间复杂度分别是什么？
  • （）若 (x) 在数组中出现的概率为 (q)，求算法的平均时间复杂度（期望比较次数）。
查看答案与解析

答案

  • 与）最好：(O(1))，最坏：(O(n))，平均（成功且等概率）：(O(n))，且成功时的期望比较次数（(\frac{n+1}{2})（
  • （）若 (x) 在数组中概率）(q)，则期望比较次数：
$$E(n)=q\cdot\frac{n+1}{2}+(1-q)\cdot n,$$

因此平均时间复杂度为 (O(n))。

解析（步骤完整）

把“数组元素与 (x) 的一次比较”作为基本操作，记比较次数为 (C)（

（）成功查找且等概：

  1. *最好情案：(a[0]=x)，只需比较 1 次，(C_{\min}=1\Rightarrow O(1))：
  2. *最坏情况（成功案：(a[n-1]=x)，比较(n) 次，(C_{\max}=n\Rightarrow O(n))。
  3. 平均情况（成功且等概率）：若 (x) 出现在位：(i)（(0\le i\le n-1)），则比较次数为 (i+1)，且
$$P(i)=\frac{1}{n}.$$

因此

$$E[C\mid \text{成功}] =\sum_{i=0}^{n-1}\frac{1}{n}(i+1) =\frac{1}{n}\cdot\frac{n(n+1)}{2} =\frac{n+1}{2} =\Theta(n).$$

（）出现概率为 (q) 的一般平：

将“成功查找”和“不成功查找”合并计算期望：

  • 成功查找概率）(q)，且（默认成功位置等概率）成功时的期望比较次数为 (\frac{n+1}{2})，
  • 不成功查找概率为 (1-q)，循环会：(i) ：0 比较：(n-1)，比较次数为 (n)，

所以总期望为

$$E(n)=q\cdot\frac{n+1}{2}+(1-q)\cdot n.$$

，(q=\frac12) 时，

$$E(n)=\frac12\cdot\frac{n+1}{2}+\frac12\cdot n=\frac{3n+1}{4}\approx\frac{3}{4}n.$$

方法总结：平均复杂度本质是“期望基本操作次数”；先写清每种情形的代价，再按概率加权求和。

难度：⭐： 考点：#顺序查找 #平均时间复杂度 #期望 #概率模型

💡 学习锦囊

📖 相关公式与知识点

  • 等差数列求和：(\sum_{k=1}^{n}k=\frac{n(n+1)}{2})。
  • 平均比较次数的写法：(E=\sum p_i\cdot c_i)。

易错点

  • 把“不成功查找”当：(n+1) 次比较（本代码中是比较数组元素次数，因此：(n) 次；若包：i<n 的判断则另计）：
  • 平均“成功查找”与“总体（含不成功）平均”混为一谈。
🔄 举一反三
  1. 若成功位置不等概率：(P(i)=\frac{2(i+1)}{n(n+1)})（越靠后概率越大），求成功时的期望比较次数。
    查看练习答案与解析

    答案：(E=\frac{2}{n(n+1)}\sum_{i=0}^{n-1}(i+1)^2=\frac{2}{n(n+1)}\cdot\frac{n(n+1)(2n+1)}{6}=\frac{2n+1}{3}=\Theta(n))。

    解析：将 (k=i+1)，用平方和公式(\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6})式

  2. 设数组已排序，用二分查找，比较次数的最优最优平均复杂度分别是什么（）(n) 为规模）。
    查看练习答案与解析

    答案：最优(O(1))，最优(O(\log n))，平与(O(\log n))与 解析（要点）：每次比较后把区间规模减半，比较次数约为 (\lfloor \log_2 n \rfloor + 1)，

二、简答题（每小题 5 分，：20 分） ​

1. 算法设计的基本步骤？ ​

查看答案与解析

答案要点

  1. 问题分析：明确目标（输出）、约束条件（输入）、边界情况与评价指标：
  2. *选择数据结构与设计策案：根据问题特性选择合适的数据表示与策略（迭代/分治/动态规：回溯/贪心等）：
  3. 描述算法：给出清晰的步骤描述（伪：流程：结构化语言），并定义关键变量与过程：
  4. *正确性证案：论证算法对所有合法输入都能得到正确输出（不变式、归纳、最优子结构等）：
  5. 复杂度分析与优化：共析时间空间复杂度，必要时改进与权衡。

难度：⭐
考点：#算法设计流程 #正确性证明 #复杂度分析

💡 学习锦囊

📖 相关公式与知识点

  • 常用正确性证明。循环不变式、数学归纳法、反证法：
  • 复杂度评价：渐近上界 (O(\cdot))、下）(\Omega(\cdot))、紧。(\Theta(\cdot))。
🔄 举一反三
  1. 简述“算法分析”通常包括哪些指标。
    查看练习答案与解析

    答案：主要包括时间复杂度、空间复杂度；在工程中也会考虑常数因子、缓）IO、可并行性与稳定性等与 解析：理论课以渐近复杂度为主；实际实现需结合平台与数据分布可

2. 能用递归解决的问题应满足哪些基本条件。 ​

查看答案与解析

答案要点

  1. 可分解为规模更小的同类子问题：原问题可转化为一个或多个结构相同、规模更小的子问题：
  2. *递归必须有终止条件（基本情形案：存在可直接求解的最小规模输入，且能被触达态
  3. *规模严格缩小且调用次数有案：每次递归都使规模朝终止条件推进，否则会无限递归。

难度：⭐
考点：#递归 #递归终止条件 #递归分解

💡 学习锦囊

📖 相关公式与知识点

  • 递归通常对应递推式，用于复杂度分析：(T(n)=aT(n/b)+f(n)) 。(T(n)=aT(n-1)+f(n))。
🔄 举一反三
  1. 为什么“有终止条件”还不够？还需要“规模严格缩小”？
    查看练习答案与解析

    答案：如果每次递归不缩小规模，即使写了终止条件也可能永远到不了终止状态（例如不断对同一规模调用自己），仍会无限递归与 解析：终止条件是“存在”，规模缩小是“可达”：

3. 简述动态规划与分治法的异同。 ​

查看答案与解析

答案要点

  • *相同案：都把原问题分解为子问题，再由子问题解组合得到原问题解；都依赖“最优子结构/可组合性”：
  • **不同：*：
    • *分治案：子问题通常相互独立：不重：；递归求解再合并结果（如归并排序）：
    • 动态规案：子问题通常重叠*；用“记忆化/表格法”复用子问题结果，避免重复计算；常配合“阶：状态转移”建模。

难度：⭐： 考点：#动态规划 #分治 #重叠子问题 #最优子结构

💡 学习锦囊

📖 相关公式与知识点

  • DP 三要素：状态定义、状态转移方程、边界与遍历顺序：
  • “重叠子问题”是 DP 相比分治的关键差异点：
🔄 举一反三
  1. 举一个“分治适用：DP 不占优势”的例子，并说明原因。
    查看练习答案与解析

    答案：归并排序与 解析：子问题互不重叠，分治每个子问题只算一次；DP 的缓存并不会减少工作量。

  2. 举一个“DP 明显优于纯分治”的例子，并说明原因。
    查看练习答案与解析

    答案：斐波那契数列与 解析：(F(n)=F(n-1)+F(n-2)) 子问题大量重叠；DP/记忆化能把指数级降为线性：

4. 简述贪心法适用问题应具有的性质。 ​

查看答案与解析

答案要点

  1. 贪心选择性质：存在一种局部最优选择策略，使得每一步做出的局部最优选择最终能导向全局最优解析
  2. 最优子结构性质：问题的最优解包含子问题的最优解；做出一次选择后，剩余部分仍是同类规模更小的最优化问题。

难度：⭐： 考点：#贪心 #贪心选择性质 #最优子结构

💡 学习锦囊

📖 相关公式与知识点

  • 贪心正确性证明常见套路：交换论证（exchange argument）、归纳证明、反证。
🔄 举一反三
  1. 说明“最优子结构”与“贪心选择性质”哪个更强？为什么？
    查看练习答案与解析

    答案：贪心选择性质更强与 解析：很子DP 问题有最优子结构但不具备贪心选择性质，无法用每步局部最优直接得到全局最优（）0/1 背包）：

三、算法设计题（每小题 15 分，：30 分） ​

1. (k) 个有序序列的 2 路合并：给出最优与最差合并顺序，并写出伪码： ​

已知合并长度：(m,n) 的两序列需要比较(m+n-1) 次。设 (k) 个序列长度为 (l_1,l_2,\dots,l_k)。

查看答案与解析

答案（结论）

  • 最优（比较次数最少）：每次都合并当前最短的两个序列长度（哈夫曼式合并最优合并模式）：
  • 最差（比较次数最多）：每次都合并当前最长的两个序列长度与

解析（为什么这样最优）

每次合并会产生一个新长度 (l=l_i+l_j)，并把该长度继续参与后续合并。一次合并的代价：(l_i+l_j-1)，而新长度会在后续再次被多次“累加进代价”。因此，为了让“被重复参与的长度”尽可能小，应优先合并短序列（与哈夫曼编码的最优加权路径长度同构）：

*伪码（最优合并：最小堆：

txt
OptimalMergeCost(lengths[1..k]):
  build a min-heap H with all lengths
  cost = 0
  while H.size > 1:
    x = extractMin(H)
    y = extractMin(H)
    cost += (x + y - 1)
    insert(H, x + y)
  return cost

*伪码（最差合并：最大堆间

txt
WorstMergeCost(lengths[1..k]):
  build a max-heap H with all lengths
  cost = 0
  while H.size > 1:
    x = extractMax(H)
    y = extractMax(H)
    cost += (x + y - 1)
    insert(H, x + y)
  return cost

*复杂度分析

  • 建堆 (O(k))，每次取：插入 (O(\log k))，循：(k-1) 次：
    • 总时间(O(k\log k))
    • 额外空间 (O(k))

难度：⭐⭐⭐
考点：#最优合并模式 #贪心 #优先队列 #哈夫曼思想

💡 学习锦囊

📖 相关公式与知识点

  • “最优合并模式”可视为哈夫曼树：每次取最小两个权值合并：
  • 代价结构：合并产生的新长度会在后续被重复计算，因此早期合并顺序影响很大。

易错：

  • 只写“每次合并最短两段”而不给出可执行的堆实：伪码：
  • 把比较次数写：(m+n) 而漏。(-1)。
🔄 举一反三
  1. 设长度为 ([2,3,4,7])，求最优合并的总比较次数。
    查看练习答案与解析

    答案与*27**与

    解析：

    • 合并 2 ：3 ：5，代：4：
    • 合并 4 ：5 ：9，代：8（(4+5-1=8)）；
    • 合并 7 ：9 ：16，代：15：
    • 总计 (4+8+15=27)算 因此正确总比较次数为 27，
  2. 若合并代价改：(m+n)（没（(-1)），最优策略是否改变？
    查看练习答案与解析

    答案：不改变，仍是每次合并最短两段与 解析：(-1) 是常数偏移，不改变“让大长度尽量晚出现”的核心贪心结构：

2. 采用分治法求整数序列中的最大与最小元素，写出思路与伪码。 ​

查看答案与解析

*答案（思路：

将区：([l,r]) 二分）([l,mid]) ）([mid+1,r])，分别递归求左右区间的 ((\min,\max))，再合并得到整段：((\min,\max))：

伪码

txt
MaxMin(a, l, r):
  if l == r:
    return (a[l], a[l])         // (min, max)
  if r == l + 1:
    if a[l] < a[r]:
      return (a[l], a[r])
    else:
      return (a[r], a[l])
  mid = (l + r) // 2
  (min1, max1) = MaxMin(a, l, mid)
  (min2, max2) = MaxMin(a, mid+1, r)
  return (min(min1, min2), max(max1, max2))

*复杂度分析

递推）(T(n)=2T(n/2)+O(1)\Rightarrow T(n)=O(n))。比较次数方面，该算法能做到接近最优（）(3n/2-2) 次比较）。

难度：⭐： 考点：#分治 #最大最小 #递归合并 #比较次数优化

💡 学习锦囊

📖 相关公式与知识点

  • 分治递推：(T(n)=2T(n/2)+O(1)\Rightarrow O(n))。
  • 比较次数最优下界：同时找最大最小至少需：( \lceil 3n/2 \rceil - 2 ) 次比较（可用成对比较法达到）：

思路分析

把“最优最小”看成可合并的局部信息：左右区间各自：max/min 合并只需 2 次比较。

🔄 举一反三
  1. 用“成对比较法”在一次扫描中求最大最小，比较次数是多少？
    查看练习答案与解析

    答案：约 (3n/2-2) 次（(n) 为偶数时精确（(3n/2-2)）。 解析：每对元素先比较 1 次分出大/小，再分别与当前 max/min 比较：1 次，：3 ：对：

四、算法分析题（每小题 10 分，：20 分） ​

1. 给定赋权无向：(G=(V,E))，求最小权顶点覆盖，给出具体结果与算法设计思路： ​

（题图见同目。images/。

查看答案与解析

答案（具体结果）

由题图可读出各顶点权值：

  • (w(1)=1,;w(3)=1,;w(4)=1,;w(5)=1,;w(7)=10,;w(2)=100,;w(6)=100)

边集包含右侧三角：((2,4),(2,5),(4,5)) 以及囊7 相连：((7,1),(7,3),(7,6),(7,4))：

  1. 处理三角案({2,4,5})：要覆盖：((4,5)) 必须：4 ：5；若不：2，则 ((2,4)) ：((2,5)) 只能靠同时间4间 覆盖。由：(w(2)=100) 很大，最优选择：({4,5})，权重为 (1+1=2)，
  2. *处理顶点 7 相关案：边 ((7,4)) 已被 4 覆盖；剩案((7,1),(7,3),(7,6))案
    • 案7：一次覆盖三条边，代：(w(7)=10)
    • 不案7：必须：({1,3,6})，代：(1+1+100=102) 因此应：7：

综上，最小权顶点覆盖为：

$$U^\*=\{4,5,7\},\qquad W(U^\*)=w(4)+w(5)+w(7)=1+1+10=12.$$

*答案（算法思路概述：

可用**分支限界法（Branch and Bound）*求解最小权顶点覆盖（NP-困难问题的精确解法之一）：

  1. *状与解向案：对每个顶点 (v_i) ：(x_i\in{0,1})，表示是否选入覆盖集合 (U)并
  2. *可行性判案：当对所有边 ((u,v)\in E) 都满：(x_u=1) ：(x_v=1) 时，该解为顶点覆盖：
  3. 目标函数：最小化 (\sum_{v_i\in V} w(v_i),x_i)：
  4. *搜索案：按某种顺序依次决定顶点：0/1（左分支选入、右分支不选入）。
  5. 下界（限界函数）：对“尚未覆盖的边”，构造一个快速可计算的权重下界（例如基于未覆盖边的端点最小权估计），用以剪枝：若当前已选权：+ 下界 ：当前最优解，则剪去该分支子
  6. 结点选择策略（优先队列）：用优先队列按“当前已选权：+ 下界”从小到大扩展结点（Best-First）：

*为什么需要下案：仅按“权重小优先”并不能保证有效剪枝；要想在指数搜索中尽快收敛，需要一个尽可能紧的下界：

方法总结：NP-困难的精确求解通常＝搜索+ 剪枝；剪枝依赖下界估计的质量。

难度：⭐⭐⭐
考点：#最小权顶点覆盖 #分支限界 #下界剪枝 #优先队列

💡 学习锦囊

📖 相关公式与知识点

  • 顶点覆盖：对每条边至少选一个端点：
  • 分支限界三件套：状态表。+ 下界函数 + 结点扩展策略。

易错点

  • 把“顶点覆盖”与“独立集/匹配”概念混淆：
  • 只写“用优先队列”但不给出可行性检查与剪枝依据。
🔄 举一反三
  1. 写出“可行性检查”的伪码（给：(x_i) 判断是否为顶点覆盖）。
    查看练习答案与解析

    答案（伪码）。

    txt
    IsVertexCover(x):
  for each edge (u,v) in E:
    if x[u] == 0 and x[v] == 0:
      return false
  return true

    解析：只要存在一条边两端都未选入，就不满足覆盖：

  2. 若图是二分图，最小（不带权）顶点覆盖可用什么定理多项式求解析
    查看练习答案与解析

    答案：Kőnig 定理（最大匹配大：= 最小顶点覆盖大小），可先求最大匹配再导出最小顶点覆盖与 解析：该结论只适用于二分图且是“不带权/或特殊权重”情形，带权版本需用其他方法：

2. 用动态规划求最长递增子序列（LIS）长度，给出状态与转移，并写伪码： ​

示例：a = {2,1,5,3,6,4,8,9,7}，LIS 长度：5（如 {1,3,4,8,9}）。

查看答案与解析

*答案（状态与转移：

定义一反DP反

  • 状态：(dp[i]) 表示“以 (a[i]) 作为结尾”的最长递增子序列长度（只考虑下标 (0..i)）：
  • 初始化：(dp[i]=1)（单个元素本身长度为 1）：
  • 转移：对每个 (i)，枚举所：(0\le j<i)，若 (a[j]<a[i])，则
$$dp[i]=\max\bigl(dp[i],\;dp[j]+1\bigr).$$

最终答案：(\max_{0\le i\le n-1} dp[i])。

伪码

txt
LISLength(a[0..n-1]):
  for i = 0..n-1:
    dp[i] = 1
    for j = 0..i-1:
      if a[j] < a[i]:
        dp[i] = max(dp[i], dp[j] + 1)
  ans = dp[0]
  for i = 1..n-1:
    ans = max(ans, dp[i])
  return ans

*复杂度

  • 时间：双重循：(O(n^2))
  • 空间：(O(n))

难度：⭐： 考点：#动态规划 #最长递增子序列 #状态转移 #O(n^2)

💡 学习锦囊

📖 相关公式与知识点

  • LIS 的常见两种解法：(O(n^2)) DP（易写易懂）；(O(n\log n)) 贪心 + 二分（维次tails 数组）。

易错点

  • 条件应为严格递增：使：(a[j] < a[i])，不要误写成 (\le)：
  • (dp[i]) 的定义一定要是“以 (i) 结尾”，否则转移会写乱。
🔄 举一反三
  1. 若要求“最长非递减子序列”（允许相等），转移条件如何改？
    查看练习答案与解析

    答案：把条件 (a[j] < a[i]) 改为 (a[j] \le a[i])。 解析：非递减允许相等元素连接，DP 框架不变，只改比较符号：

  2. 给出 (O(n\log n)) 方法的核心思路（不要求完整证明）。
    查看练习答案与解析

    答案：维护数：tails[len] 表示“长度为 len 的递增子序列可能的最小结尾值”；遍历每个元素，用二分找其应更新的位置，从而保：tails 单调并实：(O(\log n)) 更新与 解析：tails 的长度就：LIS 长度；该方法求长度很快，但恢复具体序列需额外记录前驱：

你正在阅读的是会员专属文档，💕 限时特惠进行中
你尚未登录，目前新用户可获3天体验会员，去登录